import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


/**
 * 先排序，然后先固定两个数，在剩下的里面找两个数的和等于相反数，去重
 */
public class _18_四数之和 {


    @Test
    public  void  test(){
    int [] nums={2,2,2,2,2};
    System.out.println(fourSum(nums, 0));
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists=new ArrayList<>();
        if (nums==null||nums.length<4){
            return lists;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3; i++) {
            //要是后一个值和当前值相同就直接跳过
            if (i>0&&nums[i]==nums[i-1]){ continue; }
            for (int j = i+1; j < nums.length-2; j++) {
                if (j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                long twosum=nums[i]+nums[j];
                int left=j+1;
                int right=nums.length-1;
                while (left<right){
                    long sum=twosum+nums[left]+nums[right];
                    if (sum>target){
                        right--;
                    }else if (sum<target){
                        left++;
                    }else {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        if (!lists.contains(list)){
                            lists.add(list);
                        }

                        left++;
                        right--;

                    }
                }
            }
        }
        return lists;
    }
}
